1. Field of the Invention
The present invention is related to a method for decoding transform coefficients corresponding to an image, and more particularly, to a method for decoding CAVLC transform coefficients corresponding to an image.
2. Description of the Prior Art
Getting digital video from its source (a camera or a stored clip) to its destination (a display) involves a chain of components or processes. Key to this chain is the process of compression (encoding) and decompression (decoding), in which bandwidth-intensive ‘raw’ data is reduced to a manageable size for transmission or storage, and then reconstructed for display. Better compression and decompression can give a significant technical and commercial edge to a product, providing better image quality, greater reliability and more flexibility. There is therefore a keen interest in the continuing development and improvement of video compression and decompression methods and systems. The early successes in the digital video industry were underpinned by international standard ISO/IEC 13818 [1], popularly known as “MPEG-2”. Anticipation of a need for better compression tools has led to the development of two further standards for video compression, known as ISO/IEC 14496 Part 2 (commonly known as “MPEG-4”) and ITU-T Recommendation H.264/ISO/IEC 14496 Part 10 (commonly known as “H.264”).
Image signals demonstrate close correlations between spatially neighboring pixels and thus transformation into the frequency domain leads to deviation of information to the low frequency region, which enables reduction of redundancy by making use of the deviation. Therefore, the typical image encoding methods adopt a technique of subjecting image signals to an orthogonal transformation to transform them into orthogonal transform coefficients in the frequency domain, so as to achieve deviation of signal components to the low frequency region. Furthermore, the coefficient values are quantized so that small-valued coefficients are converted into zeros. A coefficient string is made by reading the coefficients in an order from the lowest in the low frequency region and is subjected to entropy coding taking advantage of the deviation of coefficient values, thus achieving efficient encoded data with reduction of redundancy.
A number of encoding techniques are known in the art. For example, one technique encodes the various parameters of a macro-block using a single variable length coding (VLC) scheme. The technique is simple to practice, however the amount of data reduction or compression is only moderately effective. Other techniques, such as context-based adaptive binary arithmetic coding (CABAC) and context-adaptive variable length coding (CAVLC), employ context adaptation and arithmetic coding to improve overall effectiveness. While both techniques feature high compression capability, CAVLC is less complex, easier to practice and requires less memory. Therefore, MPEG-4 and H.264 both adopt CAVLC for encoding data.
Please refer to FIG. 1 for a diagram illustrating an encoding method using CAVLC. FIG. 1 shows a 4×4 block 10 including 16 coefficients obtained from an image. The coefficients at the upper-left corner of the block 10 have lower spatial frequency than those at the lower-right corner of the block 10. The use of CAVLC takes advantage of the presence of a large number of coefficients quantized to zero and the order of the remaining non-zero coefficients. CAVLC exploits the coefficients' statistical correlation by first scanning the block 10 in a zigzag manner, indicated by a dotted arrow in FIG. 1, approximately from the coefficients with the lowest spatial frequency to the highest into a one-dimensional array. The zigzag scan produces a bitstream of (0, 3, 0, 1, −1, −1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0) representing the block 10. Among the non-zero coefficients of the bitstream, the coefficients of “+1” or “−1” are trailing-one coefficients, the zero coefficients appearing after the last non-zero coefficients (in the zigzag scan order) are trailing-zero coefficients, while the zero coefficients appearing before the last non-zero coefficients (in the zigzag scan order) are non-trailing zero coefficients,
The encoding of the bitstream based on CAVLC proceeds as follows. First, the number of non-zero and trailing-one coefficients are encoded as “total_coefficient” and “trailing_ones”, respectively. Second, the sign of each trailing-one coefficient is encoded in “trailing_one_sign”. Then the levels of the remaining non-zero coefficients are encoded in “level”. Lastly, the number of non-trailing zero coefficients and their respective run before values (block position information) are encoded in “total_zero” and “run-before”, respectively. In FIG. 1 the “trailing_ones” is clipped at 3 and the remaining trailing-one coefficients are encoded in “total_coefficient”. After CAVLC encoding, a plurality of transform coefficients {5, 3, +, −, −, 1, 3, 3, 1, 0, 0, 1, 1} can be generated from the block 10 and are described in more detail as follows:
“total_coefficient”=5
“trailing_ones”=3
“trailing_one_sign”=+, −, −
“level”=1, 3
“total_zero”=3
“run-before”=1, 0, 0, 1, 1
In the MPEG-4 and H.264 standards, decoding method are not specified. There are therefore various techniques used to decode the coefficients of the block 10 from the transform coefficients after CAVLC coding. Conventionally, a reference software implementation uses pattern-matching to obtain the number of coefficients and the number of trailing ones. In this software implementation, pattern matching is used between the codes in an encoder lookup table (LUT) and the bits at the head of the bitstream. Other implementations use LUTs to obtain the number of coefficients and the number of trailing ones. However, because of the size of the tables is large in order to accommodate all of the possible inputs, the use of these tables is not efficient and is slow. Similarly, LUTs are used in prior art implementations to obtain the number of total zeros, and have the same limitations as those implementations to obtain the number of coefficients and the number of trailing ones.